package com.sourcetrip.algorithm.sort.insertion;

import com.sourcetrip.algorithm.abs.AbstractCustomedObjectSort;

/**
 * @author: ZhouBert
 * @date: 2020/12/29
 * @description: 十大排序算法之四：插入排序（的对象比较版本）的优化版本 --
 * 优化方向：
 * 将一个个交换改为找到位置以后进行整体移动。
 * （这样可以虽然不会较少比较次数，但是可以减少交换的代码）
 */
public class InsertionCustomedSortV1<E> extends AbstractCustomedObjectSort<E> {

	/**
	 * 总体来说 inner while 更好！老师果然牛逼！
	 * @param objectArr
	 */
	@Override
	protected void sortArr(E[] objectArr) {
		sortByInnerWhile(objectArr);
	}


	/**
	 * 全部比较完毕以后，再进行整体移动
	 *
	 * @param arr
	 */
	private void sortByDoubleFor(E[] arr) {
		int size = arr.length;
		int tempIndex = 0;

		for (int index = 1, swapIndex = -1; index < size; index++) {
			tempIndex = index;
			for (int i = index - 1; i >= 0; i--) {
				if (compare(arr[i], arr[tempIndex]) > 0) {
					swapIndex = i;
				}
			}
			//此时确定了 插入位置
			if (swapIndex != -1) {
				//将位置进行交换
				//swap(swapIndex, tempIndex);
				//整体进行移动
				E temp = arr[tempIndex];
				for (int i = tempIndex; i > swapIndex; i--) {
					arr[i] = arr[i - 1];
				}
				arr[swapIndex] = temp;
				swapIndex = -1;
			}

		}
	}

	/**
	 * 这个跟上个相比，步骤优化地更加简单了：
	 * 上一个是通过得到了 swapIndex 之后，再整体移动；
	 * 这个是找到一个不是 swapIndex 就进行移动，这样更“省脑力”
	 * --
	 * 易错点：
	 * 1.i > -1 的判断条件；
	 * 2.compare(arr[i], cur) cur 的使用，索引的位置会变，但是 cur 不变！
	 * @param arr
	 */
	private void sortByInnerWhile(E[] arr) {
		int size = arr.length;
		for (int index = 1; index < size; index++) {
			//保留当前位置
			E cur = arr[index];
			int i = index - 1;
			while (i > -1 && compare(arr[i], cur) > 0) {
				arr[i + 1] = arr[i--];
			}
			arr[i + 1] = cur;
		}
	}
}
